#pragma once
#include <type_traits>
#include <iostream>
using std::ostream;

#include "../public/constants.hpp"
#include "../public/exception.hpp"
#include "../allocator/defaloc.hpp"
#include "../iterator/iterator_traits.hpp"

#include "../container/list.hpp"
#include "../container/vector.hpp"
#include "../functor/hashfunc.hpp"
#include "../functor/functor_ease_dump.hpp"


namespace bla{
	static const _containerSizeType _HASHMAP_BUCKET_SIZE_NUM = 30;
	static const _containerSizeType _HASHMAP_BUCKET_SIZE_ARRAY[_HASHMAP_BUCKET_SIZE_NUM] = {
		11,			23,			53,			97,			193,
		389,		769,        1543,		3079,		6151,
		12289,		24593,      49157,		98317,		196613,
		393241,		786433,     1572869,	3145739,	6291469,
		12582917,	25165843,   50331653,	100663319,	201326611,
		402653189,	805306457,  1610612741,	3221225473ul, 4294967291ul };
	template<typename _type>
	class hashtableIterator {
	public:
		//using define
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;
		using valueType = _type;
		using pointerType = _type * ;
		using referenceType = _type & ;
	public:
		//the vector which this->_group belongs to
		vector<list<valueType>>* _mem;
		//the vector loc which this->_cur belongs to
		vectorIterator<list<valueType>> _group;
		//when _group not end, should pointer to one detailed data, cannot be the end of list
		//when _group end, this is an empty iterator
		listIterator<valueType> _cur;
	public:
		hashtableIterator() 
			:_mem(nullptr), _group(vectorIterator<list<valueType>>()), _cur(listIterator<valueType>())
		{

		}
		hashtableIterator(vector<list<valueType>>* _pvl,
			vectorIterator<list<valueType>> _vi,
			listIterator<valueType> _li
			):_mem(_pvl), _group(_vi), _cur(_li){ ; }
		hashtableIterator(const hashtableIterator<valueType>& hi)
			: _mem(hi._mem), _group(hi._group), _cur(hi._cur){; }
		hashtableIterator<valueType>& operator=(const hashtableIterator<valueType>& hi) {
			if (&hi == this) return *this;
			else {
				this->_mem = hi._mem;
				this->_group = hi._group;
				this->_cur = hi._cur;
				return *this;
			}
		}

		referenceType operator *() { return *this->_cur; }
		const referenceType operator *()const { return *this->_cur; }
		pointerType operator ->() { return &(operator*()); }
		const pointerType operator ->()const { return &(operator*()); }

		hashtableIterator<_type>& operator ++() {
			this->_cur++;
			if (this->_cur == (*(this->_group)).end()) { //this->_cur is the last
				while (true) {  //not in the end
					//find the loc where list inside is not empty
					this->_group++;
					if (this->_group == this->_mem->end()) break;
					if (!(*(this->_group)).empty()) {
						this->_cur = (*(this->_group)).begin();
						break;
					}
				}
				if (this->_group == this->_mem->end())  //has searched to the end
				{
					this->_cur = listIterator<valueType>(); //set to empty
				}
			}
			return *this;
		};
		hashtableIterator<_type> operator ++(int) {
			auto temp = *this;
			++(*this);
			return temp;
		};
	public:
		template<typename _type>
		friend bool operator ==(const hashtableIterator<_type>& lhs, const hashtableIterator<_type>& rhs);

		template<typename _type>
		friend bool operator !=(const hashtableIterator<_type>& lhs, const hashtableIterator<_type>& rhs);
	};

	template<typename _type>
	bool operator==(const hashtableIterator<_type>& lhs, const hashtableIterator<_type>& rhs) {
		return (lhs._mem == rhs._mem) && (lhs._group == rhs._group) && (lhs._cur == rhs._cur);
	}

	template<typename _type>
	bool operator!=(const hashtableIterator<_type>& lhs, const hashtableIterator<_type>& rhs) {
		return !(lhs == rhs);
	}

	/*
	 * template para:
	 * _keytype : type of key, _valtype: type of value(the whole data include key!)
	 * _hash: hashfunction, is a functor
	 * _ExtractKeyFunctor: extract key from the whole value data, is a functor
	 * _EqualKeyFunctor: how to compare two keys, is a functor

	 * note: forcely use the _defaloc allocator inside,
	 * note2: key cannot be equal, in other words: if one key occured, it cannot be inserted again
	 */
	 /*
	  * when use as unordered_set
	  * :	 * _hash: suggest using the default value: the default is _defhashFunctor<_keytype> class
	  * _identitySingleFunctor: suggest using the default value: the default is _identitySingleFunctor<_keytype> class
	  * _EqualKeyFunctor: suggest using the default value: the default is _identitySameTypeCompareFunctor<_keytype> class
	  */
	template<typename _keytype, typename _valtype, 
		typename _hash, typename _ExtractKeyFunctor,
		typename _EqualKeyFunctor
	>
	class hashtable {
	public:
		//using define
		using iterator = hashtableIterator<_valtype>;
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;
		using valueType = _valtype;
		using pointerType = _valtype * ;
		using referenceType = _valtype & ;

		using keyType = _keytype;
		using hashResType = _baseSizeType;
	private:
		vector<list<valueType>> _mem;
		_hash hasher;
		_ExtractKeyFunctor extractKeyer;
		_EqualKeyFunctor equalKeyer;
		sizeType _size;
		sizeType _curBucketSizeIndex;
	public:
		inline sizeType size() { return this->_size; };
		inline sizeType bucketSize() { return _HASHMAP_BUCKET_SIZE_ARRAY[this->_curBucketSizeIndex]; };
		inline const sizeType size() const { return this->_size; };
		inline const sizeType bucketSize() const { return _HASHMAP_BUCKET_SIZE_ARRAY[this->_curBucketSizeIndex]; };
	private:
		double loadFactor() {
			return (double)this->size() / (double)this->bucketSize();
		}
		hashResType getHashCode(keyType k) {
			return hasher(k);
		}
		keyType getKey(valueType v) {
			return extractKeyer(v);
		}
		bool isSameKey(keyType k1, keyType k2) {
			return equalKeyer(k1, k2);
		}

		/*
		 * try erase k
		 */
		void findAndErasePri(keyType k) {
			hashResType _bucketIndex = this->getHashCode(k) % this->bucketSize();
			for (listIterator<valueType> iter = this->_mem[_bucketIndex].begin();
				iter != this->_mem[_bucketIndex].end(); ++iter) {
				if (this->isSameKey(this->getKey(*iter), k)) {
					this->_mem[_bucketIndex].erase(iter);
					this->_size--;
					break;
				}
			}
		}

		/*
		 * rehash
		 */
		void reHash() {
			if (this->_curBucketSizeIndex == (_HASHMAP_BUCKET_SIZE_NUM - 1)) {
				throw baseException("in hashtable template class: cannot reHash, size already too big!");
			}
			else {
				this->_curBucketSizeIndex++;
				vector<list<valueType>> newMem = vector<list<valueType>>();
				for (sizeType _c = 0; _c < _HASHMAP_BUCKET_SIZE_ARRAY[this->_curBucketSizeIndex]; ++_c) {
					newMem.push_back(list<valueType>());
				}
				//this->_mem = newMem;

				const hashtableIterator<_valtype> _begin = this->getBegin();
				const hashtableIterator<_valtype> _end = this->getEnd();
				for (hashtableIterator <_valtype> _cur = _begin; _cur != _end; ++_cur) {
					hashResType _bucketIndex = this->getHashCode(this->getKey(*_cur)) % this->bucketSize();
					newMem[_bucketIndex].push_back(*_cur);
				}
				this->_mem = newMem;
			}
		}

	public:
		hashtable() : 
			_mem(vector<list<valueType>>()),
			hasher(_hash()), extractKeyer(_ExtractKeyFunctor()),
			equalKeyer(_EqualKeyFunctor()), _size(0), _curBucketSizeIndex(0)
		{
			for (sizeType _c = 0; _c < _HASHMAP_BUCKET_SIZE_ARRAY[this->_curBucketSizeIndex]; ++_c) {
				this->_mem.push_back(list<valueType>());
			}
		};

		const iterator getBegin() const {
			//vector<list<valueType>>* _mem;
			vectorIterator<list<valueType>> _tempGroup = this->_mem.begin();
			listIterator<valueType> _tempCur = (*(this->_mem.begin())).begin();
			if (_tempCur == (*(_tempGroup)).end()) { //this->_cur is the last
				while (_tempGroup != this->_mem.end()) {  //not in the end
					//find the loc where list inside is not empty
					_tempGroup++;
					if (!(*(_tempGroup)).empty()) {
						_tempCur = (*(_tempGroup)).begin();
						break;
					}
				}
				if (_tempGroup == this->_mem.end())  //has searched to the end
				{
					_tempCur = listIterator<valueType>(); //set to empty
				}
			}
			const vector<list<valueType>>* _pvl = &this->_mem;
			vector<list<valueType>>* _cpvl = const_cast<vector<list<valueType>>*>(_pvl);
			hashtableIterator<_valtype> ret(_cpvl, _tempGroup, _tempCur);
			return ret;
		}

		const iterator getEnd() const {
			vectorIterator<list<valueType>> _tempGroup = this->_mem.end();
			listIterator<valueType> _tempCur = listIterator<valueType>();
			const vector<list<valueType>>* _pvl = &this->_mem;
			vector<list<valueType>>* _cpvl = const_cast<vector<list<valueType>>*>(_pvl);
			hashtableIterator<_valtype> ret(_cpvl, _tempGroup, _tempCur);
			return ret;
		}

		/*
		 * if find k, return true
		 * else return false
		 */
		bool find(keyType k) {
			hashResType _bucketIndex = this->getHashCode(k) % this->bucketSize();
			bool isFind = false;
			for (listIterator<valueType> iter = this->_mem[_bucketIndex].begin();
				iter != this->_mem[_bucketIndex].end(); ++iter) {
				if (this->isSameKey(this->getKey(*iter), k)) {
					isFind = true;
					break;
				}
			}
			return isFind;
		}

		/*
		 * if find k, return true
		 * else return false
		 */
		bool find(keyType k, valueType& v) {
			hashResType _bucketIndex = this->getHashCode(k) % this->bucketSize();
			bool isFind = false;
			for (listIterator<valueType> iter = this->_mem[_bucketIndex].begin();
				iter != this->_mem[_bucketIndex].end(); ++iter) {
				if (this->isSameKey(this->getKey(*iter), k)) {
					isFind = true;
					v = *iter;
					break;
				}
			}
			return isFind;
		}

		/*
		 * whether there has v, not return
		 * if no v inserted, insert,
		 * else pass
		 */
		void insert(valueType v) {
			keyType k = this->getKey(v);
			hashResType _bucketIndex = this->getHashCode(k) % this->bucketSize();
			if (!this->find(k)) {
				this->_mem[_bucketIndex].push_back(v);
				this->_size++;
				if (this->loadFactor() > 1) {
					this->reHash();
				}
			}
		}

		/*
		 * whether there has v, not return
		 * if no v inserted, insert,
		 * else pass
		 */
		void erase(keyType v) {
			this->findAndErasePri(v);
		}

		hashtable(const hashtable<_keytype, _valtype, _hash,
			_ExtractKeyFunctor, _EqualKeyFunctor>& ht) = default;
		hashtable& operator=(const hashtable<_keytype, _valtype, _hash,
			_ExtractKeyFunctor, _EqualKeyFunctor>& ht) = default;

		~hashtable() { ; };

		template<typename _keytype, typename _valtype,
			typename _hash, typename _ExtractKeyFunctor,
			typename _EqualKeyFunctor
		>
		friend ostream& operator<< (ostream &os, const hashtable<_keytype, _valtype, _hash,
			_ExtractKeyFunctor, _EqualKeyFunctor>& li);
	};

	template<typename _keytype, typename _valtype,
		typename _hash, typename _ExtractKeyFunctor,
		typename _EqualKeyFunctor
	>
	ostream & operator<<(ostream & os, const hashtable<_keytype, _valtype, _hash, _ExtractKeyFunctor, _EqualKeyFunctor>& li)
	{
		//get to the first loc
		const hashtableIterator<_valtype> _begin = li.getBegin();
		const hashtableIterator<_valtype> _end = li.getEnd();
		for (hashtableIterator <_valtype> _cur = _begin; _cur != _end; ++_cur) {
			os << *_cur << " ";
		}
		return os;
	}
}
